1. Field of the Invention
This invention relates to multiprocessor and multithreaded computing systems, and particularly to a computing system which uses specialized “Set Associative Transaction Tables” and additional “Summary Transaction Tables” to speed the processing of common transactional memory conflict cases and those which employ assist threads.
2. Description of Background
Current multiprocessor and multithreaded computing systems allow the performance of a single software application to be scaled to many times the possible performance of a single threaded application. Current software and hardware systems provide for the parallel processing of multiple threads of execution. Software applications can use existing thread libraries, such as the POSIX pthread library, to control the creation of multiple threads of parallel execution. The use of multiple threads works well for applications that operate on easily partitioned tasks and data, course grain locks can be used to control access to the few shared data structures to prevent rare conflicts between the data updates of multiple threads.
Many software applications contain data structures that must be shared among multiple threads and have frequent concurrent inspections and updates of the shared data structures. These applications require additional modifications in order to obtain good scaling when using large numbers of threads. Applications which use multiple threads of execution that access shared data structures currently require the use of specialized data locking routines in order to produce a reliable outcome that is free from deadlocks and corrupted data. The majority of existing multithreaded applications in this category use fine grained software locks to achieve good performance and correct operation. Writing high performance multithreaded programs which use fine grained software locks is extremely difficult and requires expert programming skills. The lack of these skills in the software industry severely limits the production of multithreaded applications which require the use of shared data structures and therefore the usefulness of multithreaded and multiprocessor computing systems for certain application classes, including many forms of transaction processing.
Various “Transactional Memory” systems have been proposed and built to provide a simpler programming model for constructing multithreaded applications that need to control access to shared data structures. These systems allow software running on one thread of execution to optimistically assume that shared data structures can be updated without conflict with the accesses and updates of other threads of execution. The speculative updates to memory are kept “pending” until the transactional memory system confirms that no conflicts with storage accesses of other threads have occurred. The transactional memory system must be able to discard the pending speculative updates when conflicts between the storage accesses of multiple threads are detected. The existing systems range from those that rely completely on new software constructs to those that rely on a mixture of hardware and software to obtain reasonable performance. Some existing systems have very high overhead in terms of the number of instructions executed in support of the required transactional memory behavior. Other existing systems have limitations associated with data cache structures that hold the “pending” updates to memory.